package pers.sloera.leetcode.firstMissingPositive;

import java.util.BitSet;

/**
 * class pers.sloera.leetcode.firstMissingPositive
 * user sloera
 * date 2022/3/3
 */
public class Solution {
    public static void main(String[] args) {
        final Solution solution = new Solution();
        System.out.println(solution.firstMissingPositive(new int[]{1, 2, 0}));
        final int[] ints = new int[500000];
        for (int i = 0; i < ints.length; i++) {
            ints[i] = i;
        }
        System.out.println(solution.firstMissingPositive(ints));

    }

    public int firstMissingPositive(int[] nums) {
        final BitSet bitSet = new BitSet();
        for (int num : nums) {
            if (num > 0 && num <= nums.length) {
                bitSet.set(num);
            }
        }
        int res = 1;
        while (bitSet.get(res++)) ;
        return res - 1;
    }
}
